package leetcode5;

import java.util.*;

/*
* 56. 合并区间*/
public class test12 {
    /*
    * 排序*/
//    public int[][] merge(int[][] intervals) {
//        if(intervals.length == 0){
//            return new int[0][2];
//        }
//        Arrays.sort(intervals,(a,b) -> a[0] - b[0]);
//        List<int[]>  merge = new ArrayList<>();
//        for (int i = 0; i < intervals.length; i++) {
//            if(merge.size() == 0 || intervals[i][0] > merge.get(merge.size() - 1)[1]){
//                merge.add(intervals[i]);
//            }
//            else {
//                merge.get(merge.size() - 1)[1] = Math.max(intervals[i][1],merge.get(merge.size() - 1)[1]);
//            }
//        }
//        return merge.toArray(new int[merge.size()][]);
//    }
    /*
    * 滑动窗口*/
    public int[][] merge(int[][] intervals){
        if(intervals.length == 0){
            return new int[0][2];
        }
        Arrays.sort(intervals,(a,b) -> a[0] - b[0]);
        int n = intervals.length;
        List<int[]> res = new ArrayList<>();
        int i = 0;
        while (i < n){
            int j = i + 1;
            int L = intervals[i][0];
            int R = intervals[i][1];

            while (j < n && intervals[j][0] <= R){
                R = Math.max(R,intervals[j][1]);
                j++;
            }
            res.add(new int[]{L,R});
            i = j;
        }
        return res.toArray(new int[res.size()][]);
    }
}
